VOLE-PSI - Fast OPRF and Circuit-PSI from Vector-OLE

发表于 2023-02-16 更新于 2023-02-19 分类于论文翻译

VOLE-PSI：来自向量不经意线性评估的快速 OPRF 和电路 PSI

在这项工作中，我们提出了一种基于 VOLE 和 PaXoS 数据结构的批量化不经意伪随机函数（OPRF）的新构造。然后，我们将其用于标准转换，以实现来自 OPRF 的隐私集合交集（PSI）。我们的整体构造是非常高效的，具有的通信和计算能力。我们证明，与半诚实的变体相比，我们的协议可以在实际上没有开销的情况下实现恶意的安全。对于输入大小，我们的恶意协议需要 6.2 秒和不到 59MB 的通信。这相当于每个元素低于比特，这是迄今为止公布的任何 PSI 协议（半诚实或恶意）的最低数字。此外，在理论上，我们的半诚实（或恶意）协议可以实现低至（或）比特对于的元素，在元素上内插一个多项式的额外成本。作为第二个贡献，我们提出了一个扩展，即 PSI 的输出在双方之间是秘密共享的。这种函数通常被称为电路 PSI。它允许双方在秘密共享的输出上执行后续的 MPC 协议，例如，训练一个机器学习模型。我们的电路 PSI 协议建立在我们的 OPRF 构造以及 PaXoS 数据结构的另一个应用之上。我们的协议实现了半诚实的安全性，并允许高效的实现，比以前的工作快 3 倍。

1 介绍

我们考虑的是两方设置中的私有集交集（PSI）问题。这里，两个互不信任的当事人，一个是接收方，一个是发送方，各自持有一组标识符和。两方的目标是让接收方在不向双方透露任何额外信息的情况下学习交集。特别是，发送方不应该学习关于的任何信息，除了它的大小。同样地，接收方也不应该学习任何超出的大小的关于的信息。

一种常见的 PSI 方法是基于不经意的伪随机函数（OPRF）。OPRF 允许接收者输入并学习，其中是一个 PRF，而是发送者已知的。通过对每个运行 OPRF 协议，然后让发送方发送给接收方，就可以得到一个直接的 PSI 协议。然后，接收方可以在本地将发送方的 OPRF 值与自己的 OPRF 值进行比较，以了解的哪些元素在相交处。这是几个 PSI 协议的基础（见第 1.4 节），我们的第一个贡献也遵循这个范式。

虽然 PSI 本身具有有趣的应用，例如私人联系人的发现 [Kis+17; DRRT18; Kal+19]，但从实用的角度来看，PSI 的其他变体正在获得吸引力。例如，谷歌 [Ion+20] 和 Facebook [Bud+20] 都实现了 PSI 的变体，允许他们计算交集的函数，其中只有函数评估的结果和交集的大小被揭示，但没有交集本身。

这些具有计算的 PSI 协议的一般化产生了电路 PSI，其中输出并不透露给任何一方，而是在双方之间秘密共享的。更确切地说，接收方学习一个随机向量，发送方学习，如果对应于交集中的一个元素，则，否则。请注意，这意味着即使是交集的大小也不会透露给任何一方。我们还可以允许发送方（和 / 或接收方）为每个输入一个 "关联值" 。在这种情况下，输出还包括给接收方的随机向量和给发送方的向量，这样，如果，则。

1.1 贡献

PSI：我们提出了一个基于两个构件的私有集相交的协议（第 4 节）。第一个构件是一个被称为 VOLE 的协议，在图 2 中展示。对于这个组件，我们使用了 Schoppmann 等人 [SGRR19] 的协议的改进版本。第二个构件是一个线性系统求解器，例如 PaXoS [PRTY20]，我们为我们的目的调整了它，如图 1 所示。以一种新的方式结合这两个基元，我们得到一个 OPRF 协议（图 4）。这个结构是非常高效的，在我们的计算效率版本中，每个输入需要摊销比特的通信，或者在通信优化时只需要比特。我们还证明，只需很小的开销就可以获得恶意安全。

从 OPRF 中很容易得到 PSI 协议，这是我们的最终目标。这最后一步显示在图 6 中。我们表明，这个众所周知的变换的恶意变体可以被优化，与现有技术 [PRTY20; CKT10] 相比，其开销减少了 50%。我们最终的 PSI 协议对半诚实的和恶意的对手都是安全的，我们提供了两种威胁模型的实现。该协议效率很高，在半诚实（或恶意）设置中只需要 5.4（或 6.2）秒和不到 54（或 59）MB 的通信。

电路 PSI：我们的第二个贡献是一个电路 PSI 的协议。在第 5 节中，我们表明将 PaXoS 求解器与任何 OPRF 协议一起使用会产生一个不经意的可编程 PRF（OPPRF）协议。鉴于此，我们在第 6 节中利用被称为布谷鸟哈希表的数据结构的额外帮助，构建最终协议。我们还在半诚实模型中实现了我们的电路 PSI 协议的两个变体，并表明它们的性能优于以前的最佳方法 [PSTY19]。

图 1：XoPaXoS 算法

1.2 符号

我们使用作为计算安全参数，作为统计安全参数。接收者的集合被表示为，而发送者的集合为。它们各自的大小为和。通常我们只假设两个集合的大小都是。表示集合，是的缩写。我们用箭头符号表示行向量，而元素的索引则不用它。一个集合将使用类似的符号。对于一个矩阵，我们用表示它的第行向量，表示第行和第列的元素。表示与的内积。我们用表示数值相等的声明。分配被表示为，对于某个集合，符号意味着被分配到中的一个均匀的随机元素。如果一个函数是确定的，那么我们写，而如果是随机的，我们用来表示对于。

1.3 概述

OPRF：我们现在介绍我们主要协议的简化版本。我们的核心构件是一个被称为（随机）VOLE 的函数，它允许各方对随机矢量、、和元素进行抽样，从而使。PSI 接收方将持有、而发送方将持有、。我们注意到，在 VOLE 文献中，发送方和接收方的角色通常是相反的。

双方（隐含地）抽取一个指数级大的随机矩阵。接收方定义，是以行为索引的子矩阵，然后接收方解出线性系统： $ᵀ ᵀ$ 对于未知的。现在让我们假设是一些随机的解决方案，而不是琐碎的解决方案。该协议通过让接收方发送给发送方，发送方定义了：关键的观察是： $ᵀ ᵀ ᵀ ᵀ ᵀ ᵀ ᵀ$ 特别是，对于每个来说，可以认为其中是的第行。然后，可以通过让接收者应用一个随机神谕来获得一个 OPRF，即：而发送方在任何一个处计算的输出为：为了保证效率，我们将要求是一个特殊的形式，使得求解 $ᵀ ᵀ$ 是有效的，同时也能在时间内计算。具体来说，我们将使用 PaXoS 求解器 [PTY20] 来实现这些特性。

为了实现安全，关键是接收方不能在任何其他点上计算 OPRF 函数。在上面的表述中，这实际上意味着很难找到一个，使。我们展示了如何在几乎没有开销的情况下获得这样的属性。

PSI：然后我们采用我们的 OPRF 构造作为一个子程序来获得 PSI 协议。这种传统的转变指示接收者将他们的集合输入到 OPRF 协议中，以获得的。然后发送者可以发送，这使得接收者可以识别共同的项目。在恶意设置中，我们必须说明模拟器是如何从观察中提取集合的。传统的分析 [PTY20; CKT10] 通过要求 OPRF 函数是抗第二预像的，因此每个的长度必须是比特，从而有效地实现了这一点。我们证明，事实上，抗预像性是足够的，这允许 OPRF 有位的输出，这减少了大约 33% 的通信开销，或者当时高达 50%。

可编程 OPRF：我们提出了我们的 OPRF 协议的扩展，以实现一个被称为可编程 OPRF（OPPRF）的函数 [PSTY19]。这个构件将允许发送方对 OPPRF 密钥进行采样，从而使，用于他们选择的和。在所有其他位置，的输出将是随机的。

双方首先执行一个正常的 OPRF 协议，接收方输入他们的集合并接收的，让表示 OPRF 函数。发送方求解系统： $ᵀ ᵀ$ 其中为的子矩阵，以行为索引。发送方将发送给接收方，接收方输出：对于。观察到在：如愿以偿。可以证明，在所有其他点，输出是完全随机的。一个安全问题是，可能会泄露关于的信息。事实上，PaXoS 求解器要求大于，因此可能存在多个解决方案，而 PaXoS 输出的可能会泄露信息。我们证明了 PaXoS 的这种情况，然后提出了一个在某些约束条件下均匀分布的扩展。我们称我们的扩展为 XoPaXoS，并在第 2 节中介绍了它。我们的完整协议将在第 5 节中介绍。

电路 PSI：最后，我们提出了我们的电路 PSI 扩展，允许 PSI 的输出在双方之间秘密共享。我们的协议建立在 Pinkas 等人 [PSTY19] 以前的方法上，用我们的协议取代了他们的 OPPRF 结构。为了完整起见，我们在第 6 节中介绍了这个结构。

1.4 相关工作

早期的基于 OPRF/Diffie-Hellman（DH）的 PSI 协议从 20 世纪 80 年代就已经出现了 [Mea86]，而且它们仍然是许多现代 PSI 协议的基础 [CT10; Ion+20; Bud+20]。基于 DH 的协议的优势在于其低通信成本和恒定的回合复杂度，然而这是以高计算开销为代价的。Schneider 等人 [PSSZ15] 提出了一个基于不经意传输扩展 [IKNP03]（相对于基于 OPRF）的计算效率更高的协议，以及许多衍生协议 [PSZ14; KKRT16; RR17b; OOS17]。

最近，这两种范式开始融合，并提出了各种 OPRF 构造 [DCW13; KKRT16; RR17a; PRTY19; PRTY20; CM20]，这些构造更接近于 [IKNP03]。所有这些都比 [Mea86] 有更高的通信成本，但它们大大减少了计算量。然而，正如 Chase 和 Miao [CM20] 的评估所示，协议的最佳选择往往取决于网络设置。我们的工作也遵循基于 OPRF 的方法，建立在 Pinkas 等人 [PRTY20] 最近的 PSI 协议上，但大大减少了通信。正如我们在第 7 节中的实验所显示的，我们的协议在带宽有限和大输入规模的环境中工作得特别好。关于 PSI 的不同方法的扩展概述，见 [Ion+20, 4.1 节] 和 [PSZ18, 1.2 节]。

第一个电路 PSI 协议完全基于通用技术，如乱码电路 [HEK12] 或 GMW [PSSZ15；PSZ18]。随后的工作改进了计算和通信 [CO18; PSWW18; PSTY19]，而 Pinkas 等人的线性复杂度协议 [PSTY19] 形成了目前的技术水平。他们的协议结合了一个基于多项式插值的不经意可编程 PRF（OPPRF）和一个相对较小的 GMW 电路。我们的电路 PSI 协议遵循类似的方法，但使用了我们新的 OPRF 结构，以及基于 PaXoS [PTY20] 的新颖编程方式。

2 线性求解器和 PaXoS

我们的构造利用了线性系统求解器。如前所述，我们将使用这些求解器将我们的输入集和值编码为一个向量。将存在一个函数，使得对于，并且相对于是线性的。有三个主要的性能指标是我们所关注的。第一个是速率，表示编码的紧凑程度，即个项目可以被编码为个元素的向量。最后两个指标是编码器 / 解算器和解码器 / 矩阵乘法器的运行时间。

……

3 基于 VOLE 的 OPRF

3.1 VOLE

图 2 展示了 VOLE 函数。让是某个有限域，例如。双方都没有输入。发送方得到一个随机值和一个长度为的随机向量。接收方得到一个随机向量和向量。

也就是说，的第个位置等于。我们注意到，文献中已经介绍了 VOLE 的几个定义，包括选择输入和随机变体 [App+17; BCGI18; Boy+19; WYKW20]。在之前的这些工作中，这里描述的函数可以被看作是随机反转的 VOLE。为了简单起见，我们把它称为 VOLE。

一个原始的 VOLE 生成器的实现是为每个运行一个双方的乘法协议（例如，Gilboa 乘法 [Gil99]）。最近，在开发具有亚线性通信的 VOLE 生成器方面已经取得了重大进展。Boyle 等人 [BCGI18] 在这个方向上提出了基于 LPN 假设的第一个协议。他们的两个协议，一个原始的和一个双重的变体，依赖于两种不同类型的 LPN。虽然原始变体可以通过廉价的局部线性编码从 LPN 中实例化出来，但其通信量随着输出大小的平方根而渐进式增长。另一方面，双重变体允许对数通信，但需要更多的计算。

Schoppmann 等人 [SGRR19] 提供了原始 VOLE 生成器的第一个实现，同时，Boyle 等人 [Boy+19] 提供了二进制场上的双 VOLE 实现。最近，Yang 等人 [Yan+20] 对 Schoppmann 等人 [SGRR19] 的协议进行了改进，大大降低了通信开销。他们的主要观察结果是，原始的 VOLE 发生器通过将一个大小为的随机种子相关扩展到一个大小为的伪随机相关来工作。现在，通过迭代地应用这个扩展，他们设法从一个更短的种子得到大小为的 VOLE 相关。每个扩展仍然需要的通信，但是正如 Yang 等人 [Yan+20] 所显示的，LPN 的安全参数可以被优化，所以具体的通信复杂性仍然远远低于非迭代方法。由于他们专注于 VOLE 在相关 OT 中的应用，Yang 等人 [Yan+20] 的实现仅限于二进制领域。然而，Weng 等人 [WYKW20] 将这一范式扩展到一般场上的 VOLE，他们还为其提供了恶意安全的一致性检查。在我们的实现中（第 7 节），我们使用了 Schoppmann 等人 [SGRR19] 的库的改进版本，结合了 Yang 等人 [Yan+20] 的迭代方法和 Weng 等人 [WYKW20] 的一致性检查。

图 2：随机反转的向量不经意线性评估（vole）的理想函数。

参数：有两方，一个发送方和一个接收方。令为一个域。令表示输出向量的大小。

函数：在收到发送方的和接收方的后。

如果接收方是恶意的，等待他们发送，。采样并计算。否则，
如果发送者是恶意的，等待他们发送 , . 采样并计算。否则，
采样 , , 并计算。

该函数向发送方发送、，向接收方发送，。

3.2 恶意安全的 OPRF

我们现在介绍我们在混合模型中的主要（多输入）OPRF 构造。我们的构造详见图 4，在恶意设置中实现了图 3 中的函数。我们的协议将使用两个随机口令，，。

首先，接收方将解决系统 $ᵀ ᵀ$

作为集合 X 的函数。根据行的选择，这可以对应于多项式插值、布隆过滤器求解器、PaXoS 或其他一些快速求解器，见第 2 节。回顾一下，对于所有的，持有，并且是的线性函数。另一个重要的属性是，只适用于集合中的元素，除了可忽略的概率。

双方首先调用，接收方得到，，而发送方得到，。接收方计算并将其发送给发送方，发送方计算。双方将运行一个掷硬币协议，然后选择一个随机的。

发送方将其 PRF 函数定义为：接收方输出数值： ……

4 隐私集合交集

使用我们上一节的 OPRF 协议，我们现在通过图 6 所示的众所周知的转换得到一个 PSI 协议。图 5 中给出了 PSI 的理想函数。给定一个恶意或半诚实的 OPRF，这个变换分别实现了恶意或半诚实的安全。虽然一般的变换是已知的，并且被 [CKT10; DCW13; RR17a; PRTY19; PRTY20; CM20] 隐含地或明确地使用，但我们提供了一个在恶意设置中的严格分析，与 [CKT10; PRTY20] 相比，我们的通信减少了 20% 到 50%。

OPRF 到 PSI 的转换工作如下。PSI 的接收者将他们的集合发送给 OPRF 函数，并收到所有的。发送方发送给接收方，接收方可以计算。

为了确保该协议的正确性，关键是和值之间不存在任何虚假的碰撞。特别是，由于是一个随机函数，有可能出现。在半诚实设置中，标准方法是将的输出域定义为，其中。由于在随机取样之前，和是固定的，所以任何导致的概率纯粹是一个统计问题。尤其是：如果我们对采取联合约束，碰撞的总体概率是。

在恶意设置中，由于模拟器必须通过观察发件人的查询和的值来提取发件人的集合，情况就复杂了。民间的方法是提取，其中是发送方查询的输入集合。然而，如果存在不同的，，使，那么对于每一个，都会提取一个以上的。

存在不同的，，同时的概率最多为，其中。因此，当时，预计会出现这种情况。因此，在民俗分析和 [CKT10; PRTY20] 中，要求，以使安全论证成立。

我们现在提出一个新的提取程序，允许。在我们的协议中，这有效地减少了发送方的通信量的一半，因此当时，整体通信量减少一半。

我们的提取程序是只提取，如果它是独特的。直观地说，安全性仍然成立的原因是，内的碰撞不太可能与接收者的集合发生碰撞。特别是，接收者的集合首先被固定，然后对函数进行采样。因此，存在一个和，但的概率最多为：因此，如果，概率是。具体来说，如果，，那么发送者将不得不进行预期的次查询，以期望通过民俗分析进行区分，而不是次查询。

定理 2：协议在混合模型中实现了针对恶意对手的函数。

证明：考虑一个恶意的发件人。模拟器与发件人的互动为：

模拟器扮演的是的角色。模拟器观察所有的信息。让为所有此类的集合。
当发送者发送时，模拟器计算并提取并将发送至。

首先，在不存在任何碰撞的条件下，很容易验证上述模拟是正确的，而且是不可区分的。

现在考虑一些碰撞。观察一下，如果其中一个有明显的概率，模拟器只需要提取，，如果有一个明显的概率在中，，让我们假设。因此，考虑的概率，对于一些。因为，发送者发现这样一个（目标预象）碰撞的概率是。

考虑一个恶意的接收器。模拟器如下：

模拟器扮演的角色是。
当接收者向发送时，模拟器观察到，并像那样将发送回去。
模拟器将转发到，并收到作为回应。
模拟器将计算为包含所有以及来自的统一值，从出来。模拟器发送。

除了假项目是从而不是中取样外，这个模拟与真实协议完全相同。然而，由于，这种变化是无法区分的。

图 5: 隐私集合交集的理想函数

参数：有两方，一个发送方有一组，一个接收方有一组密钥。让 , , 为公共参数，其中。

函数：在收到发送方的和接收方的时。如果，则中止。如果接收者是恶意的，并且，则中止。如果接收者是诚实的，并且，则中止。

该函数向接收器输出。

图 6：实现 PSI 函数的协议。

参数：有两方，一个有集合的发送方和一个有集合密钥的接收方。

在半诚实的设置中，令。在恶意设置中，让。令为 OPRF 函数，，，输出长度为。

协议：

发送方发送，接收方发送到。接收方收到。
对于，发送者向发送，并接收回。
发送方以随机顺序向接收方发送。
接收者输出。

5 可编程的 OPRF

我们现在把注意力转向构建我们的电路 PSI 协议。为了实现这一点，我们首先构建一种被称为遗忘的可编程 PRF（OPPRF）的协议。其函数如图 7 所示。发送方有一组输入对。该函数对一个密钥进行采样，使，并在所有其他输入点输出一个随机值。然后，接收器在输入点上获得所有的。

……

6 电路 PSI

我们现在从我们的 OPPRF 构建一个电路 PSI 协议。我们的构造（图 10）建立在 Pinkas 等人 [PSTY19] 的方法上，使用了上一节中我们新颖的 XoPaXoS 和基于 VOLE 的 OPPRF。正如我们将在实验中看到的（第 7 节），与 [PSTY19] 相比，这意味着显著的速度提升。图 9 中给出了电路 PSI 的理想函数。它允许发送方和接收方输入一组关联值，这些关联值将与交集中的元素一起被秘密共享。与交集中的元素相对应的关联值可以在随后的任何 MPC 阶段使用，例如可以用来计算交集的和 [Ion+20] 或内积 [SGRP19]。

……

7 性能评估

7.1 理论对比

这里比较的所有协议主要是基于高效的对称密钥原语（DH-PSI 协议除外）并且可以用运行时间进行实例化。由于这些协议在渐进上是相似的，因此比较它们变得很困难。正如我们在下面所做的，一个衡量标准是实现协议并比较它们的运行时间。然而，实现的质量对运行时间有很大影响。可以说，一个更客观的指标是总通信量，它与实现方式无关。

……

7.2 实验评估

实施：我们用 C++ 实现我们所有的协议。我们使用 Schoppmann 等人 [SGRR19] 的 VOLE 实现的扩展版本，支持迭代引导 [Yan+20] 和恶意安全的一致性检查 [WYKW20]，并假设具有规则噪声的 LPN [见 BCGI18；WYKW20]。在我们的 PaXoS 实现中，为了计算布谷鸟图的 2 核，我们使用了 igraph [Igr]，并且我们依靠 libOTe [Rin] 来实现遗忘传输和我们电路 PSI 协议中使用的 GMW 实现。

为了将我们的协议与以前的工作 [KKRT16; CM20; PRTY20; PSTY19] 进行比较，我们在不同的网络设置下进行了实验。为此，我们使用了两个亚马逊 EC2 M5.2x 大型虚拟机，每个都有 8 个 2.5GHz 的内核和 32GiB 的内存。为了具有可比性，我们将每个协议限制在一个核心上。在局域网中，在没有任何人为限制的情况下，我们测量了机器之间的带宽为 5Gbps。对于带宽较低的设置，我们使用 Wondershaper [HGS] 来限制传入和传出的流量。

PSI：在这里，我们将我们的半诚实和恶意的 PSI 实现与 Kolesnikov 等人 [KKRT16]、Chase 和 Miao [CM20] 以及 Pinkas 等人 [PRTY20] 的作品进行比较。Kolesnikov 等人的协议 [KKRT16] 特别快，但有一个相对较大的通信开销。另一方面，Chase 和 Miao [CM20] 的半诚实协议具有较低的通信开销，但计算成本较高。最后，Pinkas 等人的 PaXoS 协议 [PRTY20] 具有快速计算的特点，但与 [CM20] 相比，通信量增加。我们没有与 SpOT-light 协议 [PTY19] 进行比较，因为 [CM20] 在高带宽环境下优于它，而我们的协议比 SpOT-low 的通信量还要低。

我们在半诚实环境下的评估结果见表 2。正如预期的那样，[KKRT16] 在局域网设置中优于所有其他协议，但在带宽减少的情况下效果较差。对于中等输入规模和带宽，[CM20] 和 [PRTY20] 有时优于我们的协议和 [KKRT16]。我们的协议在中低带宽环境下和大的输入规模下特别亮眼，考虑到其低通信成本，这是可以预期的。

在恶意设置中，技术现状由 [PRTY20] 提出。同样，我们比较了不同带宽设置下的通信和运行时间，并在表 3 中列出了我们的结果。虽然在局域网中，[PRTY20] 有时会优于我们的实现，但随着带宽的减少，我们的速度始终较快。

由于我们的协议所依据的矢量 OLE 实现使用了 Yang 等人 [Yan+20] 的迭代引导方法，我们的协议有一个独特的特点，即部分计算可以在一次性的、与数据无关的设置阶段进行。我们对这个设置阶段的实施可以通过调整 LPN 参数（以及引导迭代的大小）来改进，以适应输入集的大小。目前我们使用的是 [BCGI18; Yan+20] 的参数，没有进行任何额外的调整。在我们的表格中，我们用灰色强调了设置被摊销时的最佳协议。可以看出，在这种情况下，我们的协议更持续地优于以前的工作。

电路 PSI：我们还将我们的电路 - PSI 实现与最先进的协议 [PSTY19] 进行了比较。我们使用与 [PSTY19] 相同的布谷鸟散列参数，和散列函数，遵循 [PSZ18] 的分析。然而，我们注意到，对于给定统计安全级别的正确布谷鸟散列参数，文献中存在一些分歧。例如，对于，和，[PSZ18] 和 [DRRT18] 报告了相当不同的扩展因子（1.27 与 1.54）。在我们自己的实验中，我们发现安全级别近似于，对于和，需要。尽管如此，我们还是坚持使用 Pinkas 等人 [PSTY19] 使用的参数，以利于比较。

与 [PSTY19] 一样，我们的构造在最后使用了一个通用的两方计算阶段（图 10 中的第 5 步）。我们实现了这个步骤的两个变体：一个使用标准的 IKNP OT 扩展 [IKNP03] 来实现 GMW 离线阶段，另一个使用更新的 SilentOT [Boy+19]。

我们在表 4 中的结果显示，我们的协议在高带宽和低带宽环境下都优于 [PSTY19]。由于主要的通信瓶颈是 GMW 阶段，SilentOT 的变体在低通信环境下效果特别好。在局域网中，我们的 IKNP 变体在运行时间上仍然优于 [PSTY19]（他也使用了 IKNP），这显示了我们新的 OPPRF 构造的效率。

8 总结

在本文中，我们展示了如何将两个加密基元，即 VOLE 和线性系统求解器，如 (Xo) PaXoS，组合成高效的 O (P) PRF 和 PSI 协议。我们的最终协议在通信方面优于以前的工作，因此，在带宽受限的环境中运行时间方面也优于以前的工作。从理论的角度来看，我们提供了一个从 OPRF 到 PSI 的更有效的还原。

正如第 2 节中所讨论的，有许多方法可以实现我们所需要的 VOLE-PSI 的线性系统求解器。有一种方法是基于多项式插值的，它有可能导致最低的通信复杂度，但正如以前的工作所显示的，这是以昂贵的计算为代价的。本文提出的方法，使用 PaXoS，允许快速计算，但会产生较高的通信爆炸，渐进地。是否有更有效的（即更小的）数据结构，同时允许线性编码和解码，这仍然是一个开放的问题。如果这些结构可用，它们将直接改善我们协议的通信复杂性。

参考文献

[App+17] Benny Applebaum, Ivan Damg ̊ard, Yuval Ishai, Michael Nielsen, and Lior Zichron. “Secure Arithmetic Computation with Constant Computational Overhead”. In: CRYPTO (1). Vol. 10401. Lecture Notes in Computer Science. Springer, 2017, pp. 223–254.
[BCGI18] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. “Compressing Vector OLE”. In: ACM Conference on Computer and Communications Security. ACM, 2018, pp. 896–912.
[BM74] Allan Borodin and R. Moenck. “Fast Modular Transforms”. In: J. Comput. Syst. Sci. 8.3 (1974), pp. 366–386.
[Boy+19] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. “Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation”. In: ACM Conference on Computer and Communications Security. ACM, 2019, pp. 291–308.
[Bud+20] Prasad Buddhavarapu, Andrew Knox, Payman Mohassel, Shubho Sengupta, Erik Taubeneck, and Vlad Vlaskin. “Private Matching for Compute”. In: IACR Cryptol. ePrint Arch. 2020 (2020), p. 599.
[CKT10] Emiliano De Cristofaro, Jihye Kim, and Gene Tsudik. “LinearComplexity Private Set Intersection Protocols Secure in Malicious Model”. In: ASIACRYPT. Vol. 6477. Lecture Notes in Computer Science. Springer, 2010, pp. 213–231.
[CM20] Melissa Chase and Peihan Miao. “Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF”. In: CRYPTO (3). Vol. 12172. Lecture Notes in Computer Science. Springer, 2020, pp. 34–63.
[CO18] Michele Ciampi and Claudio Orlandi. “Combining Private SetIntersection with Secure Two-Party Computation”. In: SCN. Vol. 11035. Lecture Notes in Computer Science. Springer, 2018, pp. 464–482.
[CT10] Emiliano De Cristofaro and Gene Tsudik. “Practical Private Set Intersection Protocols with Linear Complexity”. In: Financial Cryptography. Vol. 6052. Lecture Notes in Computer Science. Springer, 2010, pp. 143–159.
[DCW13] Changyu Dong, Liqun Chen, and Zikai Wen. “When private set intersection meets big data: an efficient and scalable protocol”. In: ACM Conference on Computer and Communications Security. ACM, 2013, pp. 789–800.
[DRRT18] Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. “PIRPSI: Scaling Private Contact Discovery”. In: Proc. Priv. Enhancing Technol. 2018.4 (2018), pp. 159–178.
[Gil99] Niv Gilboa. “Two Party RSA Key Generation”. In: CRYPTO. Vol. 1666. Lecture Notes in Computer Science. Springer, 1999, pp. 116–129.
[HEK12] Yan Huang, David Evans, and Jonathan Katz. “Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?” In: NDSS. The Internet Society, 2012.
[HGS] Bert Hubert, Jacco Geul, and Simon S ́ehier. wondershaper: Command-line utility for limiting an adapter’s bandwidth. url: https: //github.com/magnific0/wondershaper.
[Igr] igraph: Library for the analysis of networks. url: https : / / github.com/igraph/igraph.
[IKNP03] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. “Extending Oblivious Transfers Efficiently”. In: CRYPTO. Vol. 2729. Lecture Notes in Computer Science. Springer, 2003, pp. 145–161.
[Ion+20] Mihaela Ion, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, Mariana Raykova, David Shanahan, and Moti Yung. “On Deploying Secure Computing: Private Intersection-Sum-with-Cardinality”. In: EuroS&P. IEEE, 2020, pp. 370–389.
[Kal+19] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. “Mobile Private Contact Discovery at Scale”. In: USENIX Security Symposium. USENIX Association, 2019, pp. 1447–1464.
[Kis+17] ́ Agnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, and Benny Pinkas. “Private Set Intersection for Unequal Set Sizes with Mobile Applications”. In: Proc. Priv. Enhancing Technol. 2017.4 (2017), pp. 177–197.
[KKRT16] Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. “Efficient Batched Oblivious PRF with Applications to Private Set Intersection”. In: ACM Conference on Computer and Communications Security. ACM, 2016, pp. 818–829.
[KS12] Kazuki Kobayashi and Tomoharu Shibuya. “Generalization of Lu’s linear time encoding algorithm for LDPC codes”. In: ISITA. IEEE, 2012, pp. 16–20.
[LM10] Jin Lu and Jos ́e M. F. Moura. “Linear time encoding of LDPC codes”. In: IEEE Trans. Inf. Theory 56.1 (2010), pp. 233–249.
[Mea86] Catherine A. Meadows. “A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party”. In: IEEE Symposium on Security and Privacy. IEEE Computer Society, 1986, pp. 134–137.
[OOS17] Michele Orr` u, Emmanuela Orsini, and Peter Scholl. “Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection”. In: CT-RSA. Vol. 10159. Lecture Notes in Computer Science. Springer, 2017, pp. 381–396.
[PRTY19] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. “SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension”. In: CRYPTO (3). Vol. 11694. Lecture Notes in Computer Science. Springer, 2019, pp. 401–431.
[PRTY20] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. “PSI from PaXoS: Fast, Malicious Private Set Intersection”. In: EUROCRYPT (2). Vol. 12106. Lecture Notes in Computer Science. Springer, 2020, pp. 739–767.
[PSSZ15] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. “Phasing: Private Set Intersection Using Permutation-based Hashing”. In: USENIX Security Symposium. USENIX Association, 2015, pp. 515–530.
[PSTY19] Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. “Efficient Circuit-Based PSI with Linear Communication”. In: EUROCRYPT (3). Vol. 11478. Lecture Notes in Computer Science. Springer, 2019, pp. 122–153.
[PSWW18] Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. “Efficient Circuit-Based PSI via Cuckoo Hashing”. In: EUROCRYPT (3). Vol. 10822. Lecture Notes in Computer Science. Springer, 2018, pp. 125–157.
[PSZ14] Benny Pinkas, Thomas Schneider, and Michael Zohner. “Faster Private Set Intersection Based on OT Extension”. In: USENIX Security Symposium. USENIX Association, 2014, pp. 797–812.
[PSZ18] Benny Pinkas, Thomas Schneider, and Michael Zohner. “Scalable Private Set Intersection Based on OT Extension”. In: ACM Trans. Priv. Secur. 21.2 (2018), 7:1–7:35.
[Rin] Peter Rindal. libOTe: A fast, portable, and easy to use Oblivious Transfer Library. url: https://github.com/osu- crypto/ libOTe.
[RR17a] Peter Rindal and Mike Rosulek. “Improved Private Set Intersection Against Malicious Adversaries”. In: EUROCRYPT (1). Vol. 10210. Lecture Notes in Computer Science. 2017, pp. 235259.
[RR17b] Peter Rindal and Mike Rosulek. “Malicious-Secure Private Set Intersection via Dual Execution”. In: ACM Conference on Computer and Communications Security. ACM, 2017, pp. 1229–1242.
[SGRP19] Phillipp Schoppmann, Adri`a Gasc ́on, Mariana Raykova, and Benny Pinkas. “Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning”. In: ACM Conference on Computer and Communications Security. ACM, 2019, pp. 13351350.
[SGRR19] Phillipp Schoppmann, Adri`a Gasc ́on, Leonie Reichert, and Mariana Raykova. “Distributed Vector-OLE: Improved Constructions and Implementation”. In: ACM Conference on Computer and Communications Security. ACM, 2019, pp. 1055–1072.
[WYKW20] Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. “Wolverine: Fast, Scalable, and Communication-Efficient ZeroKnowledge Proofs for Boolean and Arithmetic Circuits”. In: IACR Cryptol. ePrint Arch. 2020 (2020), p. 925.
[Yan+20] Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. “Ferret: Fast Extension for Correlated OT with Small Communication”. In: CCS. ACM, 2020, pp. 1607–1626.